package 面试经典150题.动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/7/8 20:35
 * @description
 */
public class T139单词拆分 {
    public static void main(String[] args) {
        String s ="leetcode";
        List<String> wordDict= new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        wordBreak(s,wordDict);
    }
    public static boolean wordBreak(String s, List<String> wordDict) {
        //目的是看能否通过修改让最后一个元素的值为true，如果可以则返回true，否则返回false
        int len =s.length();
        //boolean的默认是false
        boolean[] dp =new boolean[len+1];
        dp[0]=true;
        for(int i = 0;i<s.length();i++){
            if (!dp[i]){
                continue;
            }
            //此处有for循环，可能进行多处修改，修改为true地方我们后续当i遍历到该位置时要继续进行判定，
            // 如果有一次连续修改使得dp[len]成功改成了true,则直接break并返回true；
            // 也就是说，i遍历到每个dp[i]==true的位置，都有机会将dp[len]修改为true，
            // 如果遍历完全都没能把dp[len]修改为true，则说明无法成功拼接出字符串s
            for (String word : wordDict) {
                //startsWith方法表示的是 从第i个下标开始 s是否是以word开头的的
                if(i+word.length()<dp.length&&s.startsWith(word,i)){
                    dp[i+word.length()]=true;
                }
            }
            if(dp[len]==true){
                break;
            }
        }
        return dp[len];
    }

    //class Solution {
    //    public boolean wordBreak(String s, List<String> wordDict) {
    //        //通过看能否通过修改让最后一个元素的值为true，如果可以，则返回true，否则返回false;
    //
    //        int len=s.length();
    //        boolean[] dp=new boolean[len+1];
    //        dp[0]=true;
    //        for(int i=0;i<len;i++){
    //            if(!dp[i]){
    //                continue;
    //            }
    //            //此处有for循环，可能进行多处修改，修改为true地方我们后续当i遍历到该位置时要继续进行判定，如果有一次连续修改使得dp[len]成功改成了true,则直接break并返回true；也就是说，i遍历到每个dp[i]==true的位置，都有机会将dp[len]修改为true，如果遍历完全都没能把dp[len]修改为true，则说明无法成功拼接出字符串s
    //            for(String word:wordDict){
    //                if(i+word.length()<dp.length&&s.startsWith(word,i)){
    //                    dp[i+word.length()]=true;
    //                }
    //            }
    //            if(dp[len]==true)break;
    //        }
    //        return dp[len];
    //    }
    //}
    //https://leetcode.cn/problems/word-break/solutions/50986/dong-tai-gui-hua-ji-yi-hua-hui-su-zhu-xing-jie-shi/?envType=study-plan-v2&envId=top-interview-150
}
